package com.example.demo.leetcode.top100;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _21搜索二维矩阵II
 * @description
 * @date 2023/06/08 22:28
 * <p>
 * ******************************************************
 */
public class _21搜索二维矩阵II {

    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;


        int upper_bound = 0;
        int lower_bound = m - 1;
        int left_bound = 0;
        int right_bound = n - 1;

        return searchMatrix(matrix, target, upper_bound, lower_bound, left_bound, right_bound);

    }

    private boolean searchMatrix(int[][] matrix, int target, int upper_bound, int lower_bound, int left_bound, int right_bound) {
        System.out.println(upper_bound + "," + lower_bound + "," + left_bound + "," + right_bound);
        int m = matrix.length;
        int n = matrix[0].length;
        if (left_bound >= n || right_bound < 0 || upper_bound >= m || lower_bound < 0 || left_bound > right_bound || upper_bound > lower_bound) {
            return false;
        }
        int row_mid = lower_bound - (lower_bound - upper_bound) / 2;
        int col_mid = right_bound - (right_bound - left_bound) / 2;
        int curr = matrix[row_mid][col_mid];
        if (curr < target) {
            return searchMatrix(matrix, target, upper_bound, row_mid, col_mid + 1, right_bound)
                    || searchMatrix(matrix, target, row_mid + 1, lower_bound, left_bound, right_bound);
        } else if (curr > target) {
            return searchMatrix(matrix, target, upper_bound, row_mid - 1, left_bound, right_bound)
                    || searchMatrix(matrix, target, row_mid, lower_bound, left_bound, col_mid - 1);
        } else {
            return true;
        }
    }

    public static void main(String[] args) {
        int[][] matrix = new int[][]{{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20}, {21, 22, 23, 24, 25}};
        _21搜索二维矩阵II s = new _21搜索二维矩阵II();
        System.out.println(s.searchMatrix(matrix, 5));
    }

}
